package LeetCode;

 import java.util.ArrayList;
import java.util.List;

/**
 * @Author：DijaH
 * @Date：2023/11/28 09:39
 * @Version：1.0.0
 * @Description： 生成括号
 */
public class code22_generateParenthesis {
    public List<String> generateParenthesis(int n) {
        char[] path = new char[n << 1];
        List<String> ans = new ArrayList<>();
        process(path,0,0,n,ans);
        return ans;
    }

    /**
     *
     * @param path 在生成括号的路径
     * @param index 在 生成的 括号位置上做决定
     * @param leftMinusRight 在已经做过的区域 左括号-右括号
     * @param leftRest 还剩余多少个做括号可以匹配
     * @param ans
     */
    public static void process(char[] path,int index,int leftMinusRight,int leftRest,List<String> ans){
        if(index == path.length){
            ans.add(String.valueOf(path));
        }else{
            if(leftRest > 0){
                path[index] = '(';
                process(path,index + 1,leftMinusRight + 1,leftRest -1,ans);
            }
            if(leftMinusRight > 0){
                path[index] = ')';
                //leftRest 左边没有用
                process(path,index + 1,leftMinusRight - 1,leftRest,ans);
            }
        }
    }

    public static void main(String[] args) {
        code22_generateParenthesis res = new code22_generateParenthesis();
        List<String> strings = res.generateParenthesis(3);
        for (String string : strings) {
            System.out.println(string);
        }
    }
}
